// m

// 给定一个只包含三种字符的字符串：（，）和 *，有效的扩招字符串具有如下规则
// 1. 任何左括号(必须有相应的有右括号)
// 2. 任何右括号)必须有相应的左括号(
// 3. 左括号(必须在对应的右括号之前
// 4. *可以被视为单个右括号),或者单个左括号(，或者一个空字符串
// 5. 一个空字符串也被视为有效字符串

// 要求：验证这个字符串是否为有效字符串，如果是，则返回true，否则则返回false

// 解题思路：动态规划，时间复杂度为O(n^2)
// 1. 划分阶段： 按照字符串的结束位置进行阶段划分
// 2. 定义状态，定义状态dp[i][j]表示为：前i个字符能否通过补齐j个右括号成为有效的括号字符串
// 3. 状态转移方程
//      1. 如果s[i] == '(',如果前i-1个字符通过补齐j-1个右括号成为有效的括号字符串，则前i个字符就能通过补齐j个右括号成为有效的括号字符串（比前i-1个字符需要多补一个右括号）
//        也就是说s[i] == '(',且dp[i-1][j-1] == true,则 dp[i][j] = true
//      2. 如果s[i] == ')',如果前i-1个字符通过补齐j+1个右括号成为有效的括号字符串，则前i个字符就能通过补齐j个右括号成为有效的括号字符串（比前i-1个字符需要多补一个右括号）
//        也就是说s[i] == ')',并且dp[i-1][j+1] == true,则dp[i][j] = true
//      3. 如果s[i] == '*',*可以表示空字符串，左括号，右括号，则dp[i][j]取决于三种情况，只要其中一种情况为true，则dp[i][j] = true
//        也就是说 ，如果s[i] == '*',dp[i][j] = dp[i-1][j] || dp[i-1][j-1]
// 4. 初始条件，0个字符可以通过补齐0个右括号成为有效括号字符串即空字符串，dp[0][0] = 0
// 5. 最终结果，dp[size][0]


// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
function checkValidString(s) {
    let size = s.length
    let dp = new Array(size + 1).fill(0).map(() => new Array(size + 1).fill(false))
    dp[0][0] = true
    for (let i = 1; i < size + 1; i++) {
        for (let j = 0; j < size + 1; j++) {
            if (s[i - 1] === '(') {
                if (j > 0) {
                    dp[i][j] = dp[i - 1][j - 1]
                }
            } else if (s[i - 1] === ')') {
                if (j < i) {
                    dp[i][j] = dp[i - 1][j + 1]
                }
            } else {
                dp[i][j] = dp[i - 1][j]
                if (j > 0) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1]
                }
                if (j < i) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j + 1]
                }
            }
        }
    }
    return dp[size][0]
}

let s = "(*)"
let s2 = ""
console.log(checkValidString(s2));

function checkValidString2(str) {
    let stack = []
    let stack2 = []
    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(') {
            stack.push(i)
        } else if (str[i] === '*') {
            stack2.push(i)
        } else if (str[i] === ')') {
            if (stack.length) {
                stack.pop()
            } else if (stack2.length) {
                stack2.pop()
            } else {
                return false
            }
        }     
    }
    while (stack.length && stack2.length) {
        if (stack[stack.length - 1] < stack2[stack2.length - 1]) {
            stack.pop()
            stack2.pop()
        } else {
            return false
        }
    }
    return stack.length === 0
}